<template><div><h2 id="模板" tabindex="-1"><a class="header-anchor" href="#模板"><span>模板</span></a></h2>
<div class="language-cpp line-numbers-mode has-collapsed-lines collapsed" data-highlighter="shiki" data-ext="cpp" style="--vp-collapsed-lines:15;background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#7F848E;font-style:italic">// tt表示栈顶</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#E5C07B"> stk</span><span style="color:#ABB2BF">[N], tt </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 0</span><span style="color:#ABB2BF">;</span></span>
<span class="line"></span>
<span class="line"><span style="color:#7F848E;font-style:italic">// 向栈顶插入一个数</span></span>
<span class="line"><span style="color:#E5C07B">stk</span><span style="color:#ABB2BF">[ </span><span style="color:#C678DD">++</span><span style="color:#ABB2BF"> tt] </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> x;</span></span>
<span class="line"></span>
<span class="line"><span style="color:#7F848E;font-style:italic">// 从栈顶弹出一个数</span></span>
<span class="line"><span style="color:#ABB2BF">tt </span><span style="color:#C678DD">--</span><span style="color:#ABB2BF"> ;</span></span>
<span class="line"></span>
<span class="line"><span style="color:#7F848E;font-style:italic">// 栈顶的值</span></span>
<span class="line"><span style="color:#E5C07B">stk</span><span style="color:#ABB2BF">[tt];</span></span>
<span class="line"></span>
<span class="line"><span style="color:#7F848E;font-style:italic">// 判断栈是否为空，如果 tt > 0，则表示不为空</span></span>
<span class="line"><span style="color:#C678DD">if</span><span style="color:#ABB2BF"> (tt </span><span style="color:#C678DD">></span><span style="color:#D19A66"> 0</span><span style="color:#ABB2BF">)</span></span>
<span class="line"><span style="color:#ABB2BF">{</span></span>
<span class="line"></span>
<span class="line"><span style="color:#ABB2BF">}</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div><div class="collapsed-lines"></div></div><h2 id="模拟栈" tabindex="-1"><a class="header-anchor" href="#模拟栈"><span>模拟栈</span></a></h2>
<p><img src="@source/notes/基础算法/2.数据结构/2-1.png" alt=""></p>
<h3 id="输入样例" tabindex="-1"><a class="header-anchor" href="#输入样例"><span>输入样例</span></a></h3>
<div class="language-cpp line-numbers-mode" data-highlighter="shiki" data-ext="cpp" style="background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#D19A66">10</span></span>
<span class="line"><span style="color:#ABB2BF">push </span><span style="color:#D19A66">5</span></span>
<span class="line"><span style="color:#ABB2BF">query</span></span>
<span class="line"><span style="color:#ABB2BF">push </span><span style="color:#D19A66">6</span></span>
<span class="line"><span style="color:#ABB2BF">pop</span></span>
<span class="line"><span style="color:#ABB2BF">query</span></span>
<span class="line"><span style="color:#ABB2BF">pop</span></span>
<span class="line"><span style="color:#ABB2BF">empty</span></span>
<span class="line"><span style="color:#ABB2BF">push </span><span style="color:#D19A66">4</span></span>
<span class="line"><span style="color:#ABB2BF">query</span></span>
<span class="line"><span style="color:#ABB2BF">empty</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h3 id="输出样例" tabindex="-1"><a class="header-anchor" href="#输出样例"><span>输出样例</span></a></h3>
<div class="language-cpp line-numbers-mode" data-highlighter="shiki" data-ext="cpp" style="background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#D19A66">5</span></span>
<span class="line"><span style="color:#D19A66">5</span></span>
<span class="line"><span style="color:#ABB2BF">YES</span></span>
<span class="line"><span style="color:#D19A66">4</span></span>
<span class="line"><span style="color:#ABB2BF">NO</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h3 id="参考答案" tabindex="-1"><a class="header-anchor" href="#参考答案"><span>参考答案</span></a></h3>
<div class="language-cpp line-numbers-mode has-collapsed-lines collapsed" data-highlighter="shiki" data-ext="cpp" style="--vp-collapsed-lines:15;background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#C678DD">#include</span><span style="color:#98C379">&#x3C;iostream></span></span>
<span class="line"><span style="color:#C678DD">using</span><span style="color:#C678DD"> namespace</span><span style="color:#E5C07B"> std</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">const</span><span style="color:#C678DD"> int</span><span style="color:#ABB2BF"> N </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 1</span><span style="color:#E06C75">e</span><span style="color:#D19A66">5</span><span style="color:#C678DD">+</span><span style="color:#D19A66">10</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#E5C07B"> s</span><span style="color:#ABB2BF">[N],tt;</span></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> push</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#E06C75;font-style:italic"> x</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#E5C07B">    s</span><span style="color:#ABB2BF">[</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">tt] </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> x;</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> pop</span><span style="color:#ABB2BF">(){</span></span>
<span class="line"><span style="color:#ABB2BF">    tt</span><span style="color:#C678DD">--</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> isEmpty</span><span style="color:#ABB2BF">(){</span></span>
<span class="line"><span style="color:#C678DD">    if</span><span style="color:#ABB2BF">(tt</span><span style="color:#C678DD">></span><span style="color:#D19A66">0</span><span style="color:#ABB2BF">) cout</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#98C379">"NO"</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#ABB2BF">endl;</span></span>
<span class="line"><span style="color:#C678DD">    else</span><span style="color:#ABB2BF"> cout</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#98C379">"YES"</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#ABB2BF">endl;</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> query</span><span style="color:#ABB2BF">(){</span></span>
<span class="line"><span style="color:#ABB2BF">    cout</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#E5C07B">s</span><span style="color:#ABB2BF">[tt]</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#ABB2BF">endl;</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#61AFEF"> main</span><span style="color:#ABB2BF">(){</span></span>
<span class="line"><span style="color:#C678DD">    int</span><span style="color:#ABB2BF"> n;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">n;</span></span>
<span class="line"><span style="color:#C678DD">    while</span><span style="color:#ABB2BF">(n</span><span style="color:#C678DD">--</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#ABB2BF">        string op;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">op;</span></span>
<span class="line"><span style="color:#C678DD">        if</span><span style="color:#ABB2BF">(op </span><span style="color:#C678DD">==</span><span style="color:#98C379"> "push"</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#C678DD">            int</span><span style="color:#ABB2BF"> x;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">x;</span></span>
<span class="line"><span style="color:#61AFEF">            push</span><span style="color:#ABB2BF">(x);</span></span>
<span class="line"><span style="color:#ABB2BF">        }</span></span>
<span class="line"><span style="color:#C678DD">        if</span><span style="color:#ABB2BF">(op </span><span style="color:#C678DD">==</span><span style="color:#98C379"> "pop"</span><span style="color:#ABB2BF">) </span><span style="color:#61AFEF">pop</span><span style="color:#ABB2BF">();</span></span>
<span class="line"><span style="color:#C678DD">        if</span><span style="color:#ABB2BF">(op </span><span style="color:#C678DD">==</span><span style="color:#98C379"> "empty"</span><span style="color:#ABB2BF">) </span><span style="color:#61AFEF">isEmpty</span><span style="color:#ABB2BF">();</span></span>
<span class="line"><span style="color:#C678DD">        if</span><span style="color:#ABB2BF">(op </span><span style="color:#C678DD">==</span><span style="color:#98C379"> "query"</span><span style="color:#ABB2BF">) </span><span style="color:#61AFEF">query</span><span style="color:#ABB2BF">();</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div><div class="collapsed-lines"></div></div><h2 id="单调栈" tabindex="-1"><a class="header-anchor" href="#单调栈"><span>单调栈</span></a></h2>
<p><img src="@source/notes/基础算法/2.数据结构/2-2.png" alt=""></p>
<h3 id="参考答案-1" tabindex="-1"><a class="header-anchor" href="#参考答案-1"><span>参考答案</span></a></h3>
<div class="language-cpp line-numbers-mode" data-highlighter="shiki" data-ext="cpp" style="background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#C678DD">#include</span><span style="color:#98C379">&#x3C;iostream></span></span>
<span class="line"><span style="color:#C678DD">using</span><span style="color:#C678DD"> namespace</span><span style="color:#E5C07B"> std</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">const</span><span style="color:#C678DD"> int</span><span style="color:#ABB2BF"> N </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 1</span><span style="color:#E06C75">e</span><span style="color:#D19A66">5</span><span style="color:#C678DD">+</span><span style="color:#D19A66">10</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#E5C07B"> s</span><span style="color:#ABB2BF">[N],tt </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 0</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#61AFEF"> main</span><span style="color:#ABB2BF">(){</span></span>
<span class="line"><span style="color:#C678DD">    int</span><span style="color:#ABB2BF"> n;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">n;</span></span>
<span class="line"><span style="color:#C678DD">    while</span><span style="color:#ABB2BF">(n</span><span style="color:#C678DD">--</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#C678DD">        int</span><span style="color:#ABB2BF"> x;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">x;</span></span>
<span class="line"><span style="color:#C678DD">        while</span><span style="color:#ABB2BF">(tt</span><span style="color:#56B6C2">&#x26;&#x26;</span><span style="color:#E5C07B">s</span><span style="color:#ABB2BF">[tt]</span><span style="color:#C678DD">>=</span><span style="color:#ABB2BF">x) tt</span><span style="color:#C678DD">--</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">        if</span><span style="color:#ABB2BF">(tt</span><span style="color:#C678DD">></span><span style="color:#D19A66">0</span><span style="color:#ABB2BF">) cout</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#E5C07B">s</span><span style="color:#ABB2BF">[tt]</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#98C379">" "</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">        else</span><span style="color:#ABB2BF"> cout</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#98C379">"-1"</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#98C379">" "</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#E5C07B">        s</span><span style="color:#ABB2BF">[</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">tt] </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> x;</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div></div></template>


